{
  //  消失的数字
  // 数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？

  // 示例 1：
  // 输入：[3, 0, 1]
  // 输出：2

  // 示例 2：
  // 输入：[9, 6, 4, 2, 3, 5, 7, 0, 1]
  // 输出：8

  // 法一 排序+遍历
  function missingNumber(nums) {
    nums = nums.sort();
    // for (let i = 0; i < nums.length; i++) {
    //   if (nums[i] !== i) {
    //     return i;
    //   }
    // }
    for (let i = 0; i < nums.length - 1; i++) {
      if (nums[i + 1] - nums[i] !== 1) {
        return nums[i] + 1;
      }
    }

    // 上面只能排出非连续的数组，连续的还需要通过起始索引区分
    if (nums[0] === 0) {
      return nums.slice(-1)[0] + 1;
    } else {
      return nums[0] - 1;
    }
  }

  // 法二 排序+二分查找
  function missingNumber(nums) {
    nums = nums.sort();
    let i = 0,
      j = nums.length - 1,
      mid;

    // [0, 1, 2, 3, 4, 5, 6, 7, 9]
    while (i < j) {
      mid = Math.floor(i + j) / 2;
      if (mid === nums[mid]) {
        i = mid + 1;
      } else {
        j = mid - 1;
      }
    }

    return i;
  }

  // 法三 利用等差数列求和 时间复杂度O(n)，空间复杂度O(1)
  function missingNumber(nums) {
    let len = nums.length;
    let sum = 0;
    for (let i = 0; i < len; i++) {
      sum += nums[i];
    }

    return ((len + 1) * len) / 2 - sum;
  }

  console.log(missingNumber([3, 0, 1]));
  console.log(missingNumber([9, 6, 4, 2, 3, 5, 7, 0, 1]));
}

{
  // 给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

  // 示例 1:
  // 输入: 123
  // 输出: 321

  // 示例 2:
  // 输入: -123
  // 输出: -321

  // 示例 3:
  // 输入: 120
  // 输出: 21

  /**
   * @param {number}
   * @return {number}
   */
  let reverse = function (n) {
    // 法一 用字符串和数组的api
    // let symbol, arr = n.toString().split('');
    // if (n < 0) {
    //   symbol = arr.shift()
    // }
    // const newArr = +arr.reverse().join('')
    // return symbol ? symbol + newArr : newArr

    // 法二
    let sum = 0;
    let x = Math.abs(n);
    while (x !== 0) {
      // 从最低位开始算，sum每次 x 10 然后在加上对x取余
      // 如 0 x 10 + 123 % 10 = 3
      sum = sum * 10 + (x % 10);
      // 对x重新赋值，即去掉最后一位 如 123 -> 12
      x = Math.floor(x / 10);
    }

    // 已123为例计算过程
    // 0次  sum = 0   x = 123
    // 1次  sum = 3   x = 12
    // 2次  sum = 32  x = 1
    // 3次  sum = 321 x = 0
    return n > 0 ? sum : -sum;
  };
  console.log(reverse(123));
  console.log(reverse(-123));
  console.log(reverse(120));
}

{
  // 859. 亲密字符串
  // 给定两个由小写字母构成的字符串 A 和 B ，只要我们可以通过交换 A 中的两个字母得到与 B 相等的结果，就返回 true ；否则返回 false 。

  // 交换字母的定义是取两个下标 i 和 j （下标从 0 开始），只要 i != j 就交换 A[i] 和 A[j] 处的字符。例如，在 "abcd" 中交换下标 0 和下标 2 的元素可以生成 "cbad" 。

  // 示例 1：
  // 输入： A = "ab", B = "ba"
  // 输出： true
  // 解释： 你可以交换 A[0] = 'a' 和 A[1] = 'b' 生成 "ba"，此时 A 和 B 相等。

  // 示例 2：
  // 输入： A = "ab", B = "ab"
  // 输出： false
  // 解释： 你只能交换 A[0] = 'a' 和 A[1] = 'b' 生成 "ba"，此时 A 和 B 不相等。

  // 示例 3:
  // 输入： A = "aa", B = "aa"
  // 输出： true
  // 解释： 你可以交换 A[0] = 'a' 和 A[1] = 'a' 生成 "aa"，此时 A 和 B 相等。

  // 示例 4：
  // 输入： A = "aaaaaaabc", B = "aaaaaaacb"
  // 输出： true

  // 示例 5：
  // 输入： A = "", B = "aa"
  // 输出： false

  /*
   * @param {string} A
   * @param {string} B
   * @return {boolean}
   */

  // 解题思路
  // 1 长度不想等直接返回
  // 2 字符串想等，必须要有重复的字符
  // 3 字符串不想等，只能有两个不一样的字符，且两个不一样的字符交换之后要想等
  let buddyStrings = function (A, B) {
    if (A.length !== B.length) return false;
    if (A === B) return A.length > new Set(A).size;

    // 字符串不想等，记录同一位置不想等的字符，看最后长度是否是2，以及是否想等
    let a = '',
      b = '';
    for (let i = 0; i < A.length; i++) {
      if (A[i] !== B[i]) {
        a = A[i] + a; // 注意这里 直接对字符串取反
        b += B[i];
      }
    }
    return a.length === 2 && a === b;
    // 时间复杂度O(n)
    // 空间复杂度O(n) 用了set
  };
  console.log(buddyStrings('ab', 'ba')); // true
  console.log(buddyStrings('ab', 'ab')); // false
  console.log(buddyStrings('aa', 'aa')); // true
  console.log(buddyStrings('aaaaaaabc', 'aaaaaaacb')); // true
  console.log(buddyStrings('', 'aa')); // false
}

{
  // 14. 最长公共前缀
  // 编写一个函数来查找字符串数组中的最长公共前缀。
  // 如果不存在公共前缀，返回空字符串 ""。

  // 示例 1:
  // 输入: ["flower", "flow", "flight"]
  // 输出: "fl"

  // 示例 2:
  // 输入: ["dog", "racecar", "car"]
  // 输出: ""
  // 解释: 输入不存在公共前缀。

  // 说明:
  // 所有输入只包含小写字母 a - z 。

  /*
   * @param {string[]} strs
   * @return {string}
   */
  let longestCommonPrefix = function (strs) {
    // 取出数组的第一个字符串依次和剩余的字符串去比较。

    // 巧用数组api
    // if (!strs.length) return ''
    // const [a, ...b] = strs;
    // let result = '';
    // for (let i = 0; i < a.length; i++) {
    //   let flag = b.every(item => item[i] === a[i])
    //   if (flag) {
    //     result += a[i]
    //   }
    // }
    // return result

    // 暴力双循环
    if (strs.length === 1) {
      return strs[1];
    }

    if (!strs || strs.length === 0) {
      return '';
    }

    let res = '',
      temp = '';
    for (let i = 0; i < strs[0].length; i++) {
      temp = strs[0][i];
      for (let j = 0; j < strs.length; j++) {
        if (temp !== strs[j][i]) {
          return res;
        }
      }
      res += temp;
    }
  };
  console.log(longestCommonPrefix(['flower', 'flow', 'flight']));
  console.log(longestCommonPrefix(['dog', 'racecar', 'car']));
  console.log(longestCommonPrefix(['ams', 'flow', 'flight', 'flower']));
}

{
  // 1360. 日期之间隔几天

  // 请你编写一个程序来计算两个日期之间隔了多少天。
  // 日期以字符串形式给出，格式为 YYYY - MM - DD，如示例所示。

  // 示例 1：
  // 输入：date1 = "2019-06-29", date2 = "2019-06-30"
  // 输出：1

  // 示例 2：
  // 输入：date1 = "2020-01-15", date2 = "2019-12-31"
  // 输出：15

  // 提示：
  // 给定的日期是 1971 年到 2100 年之间的有效日期。

  /**
   * @param {string} date1
   * @param {string} date2
   * @return {number}
   */
  let daysBetweenDates = function (date1, date2) {
    // 转化成毫秒求时间戳差值
    // 然后在转化成天数
    // 巧用date api
    date1 = new Date(date1).getTime();
    date2 = new Date(date2).getTime();
    return Math.abs(date1 - date2) / 24 / 60 / 60 / 1000;

    // js比较笨方法
    // let arr1 = date1.split('-')
    // let arr2 = date2.split('-')
    // let [y1, m1, d1] = [...arr1]
    // let [y2, m2, d2] = [...arr2]
    // // 得到天数
    // let amount1 = daysAfter1970(y1, m1, d1)
    // let amount2 = daysAfter1970(y2, m2, d2)
    // return Math.abs(amount1 - amount2)
  };

  const daysOfMonth = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31];
  function isLeapYear(year) {
    return year % 400 === 0 || (year % 100 !== 0 && year % 4 === 0);
  }
  function daysAfter1970(year, mounth, day) {
    let count = 0;
    for (let i = 1970; i < +year; i++) {
      if (isLeapYear(i)) count += 366;
      else count += 365;
    }

    for (let i = 0; i < +mounth; i++) {
      if (i === 2 && isLeapYear(year)) {
        count += 29;
        continue;
      }
      count += daysOfMonth[i];
    }
    count += +day;

    return count - 1;
  }
  console.log(daysBetweenDates('2019-06-29', '2019-06-30'));
  console.log(daysBetweenDates('2020-01-15', '2019-12-31'));
}

{
  // 628. 三个数的最大乘积
  // 给定一个整型数组，在数组中找出由三个数组成的最大乘积，并输出这个乘积。

  // 示例 1:
  // 输入: [1, 2, 3]
  // 输出: 6

  // 示例 2:
  // 输入: [1, 2, 3, 4]
  // 输出: 24

  // 注意整数数组，不是正整数数组

  // 解题思路
  // 如果数组都是正数，结果是最大三个数的乘积
  // 如果又一个负数，结果还是最大三个数的乘积
  // 如果有两个以上的负数，结果可能是最小的和两个负数乘以最大的正数 或者 最大三个数的乘积
  // 如果都是负数，结果还是最大的三个数的乘积
  // 所以只需要比较最大三个数的乘积 和最小两个数和最大数的乘积 哪个大就行
  let maximumProduct = function (nums) {
    if (nums.length < 3) {
      return 1;
    }
    nums = nums.sort((a, b) => a - b);
    console.log('nums: ', nums);

    let len = nums.length;
    let sum1 = nums[len - 1] * nums[len - 2] * nums[len - 3];
    let sum2 = nums[0] * nums[1] * nums[len - 1];

    return Math.max(sum1, sum2);

    // 排序加多种条件判断
    // nums = nums.sort((a, b) => a - b);
    // let len = nums.length;
    // if (nums[len - 1] === 0) {
    //   return 0
    // } else {
    //   if (nums[0] > 0 || nums[len - 1] < 0) {
    //     // 全为正或全为负
    //     return nums[len - 1] * nums[len - 2] * nums[len - 3]
    //   } else {
    //     // 有正数 有负数
    //     return nums[len - 1] * Math.max(nums[0] * nums[1], nums[len - 2] * nums[len - 3])
    //   }
    // }
  };
  console.log(maximumProduct([1, 2, 3]));
  console.log(maximumProduct([1, 2, 3, 4]));
  console.log(maximumProduct([1, -2, 3, 4]));
  console.log(maximumProduct([1, -2, -3, 4]));
  console.log(maximumProduct([1, -2, -3, -4]));
  console.log(maximumProduct([0, -2, -3, -4]));
}

{
  // 326. 3的幂
  // 给定一个整数，写一个函数来判断它是否是 3 的幂次方。

  // 示例 1:
  // 输入: 27
  // 输出: true

  // 示例 2:
  // 输入: 0
  // 输出: false

  // 示例 3:
  // 输入: 9
  // 输出: true

  // 示例 4:
  // 输入: 45
  // 输出: false

  // 进阶：
  // 你能不使用循环或者递归来完成本题吗？

  /* 
    @param {number} n
    @return {boolean}
  */
  let isPowerOfThree = function (n) {
    // 法一 循环
    // if (n <= 0) return false
    // while (n > 1) {
    //   if (n % 3 === 0) {
    //     n = n / 3
    //   } else {
    //     return false
    //   }
    // }
    // return true

    // 法二 进制转换
    // toString将数字，将n当作10进制，转换为3进制
    // 3的幂次方，用1和0表示一定是
    // 0次方 - 1
    // 1次方 - 10
    // 2次方 - 100
    // ...
    // n次方 - 10{ 0,} ，^ 匹配开头 $匹配结尾，匹配到返回true
    return /^10{0,}$/.test(n.toString(3));

    while (n >= 3) {
      n = n / 3;
    }

    return n === 1;
  };
}

{
  // 198. 打家劫舍
  // 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
  // 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

  // 示例 1：
  // 输入：[1, 2, 3, 1]
  // 输出：4
  // 解释：偷窃 1 号房屋(金额 = 1) ，然后偷窃 3 号房屋(金额 = 3) 。
  // 偷窃到的最高金额 = 1 + 3 = 4 。

  // 示例 2：
  // 输入：[2, 7, 9, 3, 1]
  // 输出：12
  // 解释：偷窃 1 号房屋(金额 = 2), 偷窃 3 号房屋(金额 = 9) ，接着偷窃 5 号房屋(金额 = 1) 。
  // 偷窃到的最高金额 = 2 + 9 + 1 = 12 。

  let rob = function (nums) {
    if (nums.length === 0) return 0;
    if (nums.length === 1) return nums[1];
    if (nums.length === 2) return Math.max(...nums);

    // 一次循环即可
    // let max1 = 0, max2 = 0;
    // for (let i = 0; i < nums.length; i++) {
    //   if (i % 2 === 0) {
    //     max1 += nums[i]
    //   } else {
    //     max2 += nums[i]
    //   }
    // }
    // return Math.max(max1, max2);

    // 动态规划
    let prev = nums[0];
    let curr = Math.max(nums[0], nums[1]);
    let max = 0;
    for (let i = 2; i < nums.length; i++) {
      max = Math.max(curr, prev + nums[i]);
      prev = curr;
      curr = max;
    }
    return max;

    let prevMax = 0;
    let currMax = 0;
    for (const item of nums) {
      let temp = currMax;
      currMax = Math.max(currMax, prevMax + item);
      prevMax = temp;
    }
    return currMax;
  };
  console.log(rob([1, 2, 3, 1]));
  console.log(rob([2, 7, 9, 3, 1]));
}

{
  // 是否是回文串
  function palindRome(str) {
    // return str.split('').reverse().join('') === str
    for (let i = 0; i < str.length; i++) {
      if (str.charAt(i) !== str.charAt(str.length - 1 - i)) {
        return false;
      } else {
        return true;
      }
    }
  }
  // 双指针
  function palindRome(str) {
    let i = 0;
    let j = str.length - 1;
    while (i < j) {
      if (str[i] !== str[j]) {
        return false;
      }
      i++;
      j--;
    }
    return true;
  }
  // console.log(palindRome('aba'))
  // console.log(palindRome('abc'))
}

{
  // 打印出 1-1000000 之间的所有对称数(例如 121、1331 等)
  function isSymNum(start, end) {
    var arr = [];
    for (var i = start; i < end; i++) {
      // 解法有点类似回文串
      var num = +i.toString().split('').reverse().join('');
      if (i > 10 && num === i) {
        arr.push(num);
      }
    }
    return arr;
  }
  // console.log(isSymNum(1, 1000000))
}

{
  // 409. 最长回文串
  // 给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
  // 在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。

  // 示例 1:
  // 输入:
  // "abccccdd"
  // 输出:
  // 7

  // 解释:
  // 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

  /* 
    @param {string} str
    @return {number}
  */
  let longestPalindrome = function (str) {
    // 思路
    // 解题的关键是有对少对相同的字符
    // 类似与大牌，抽到一对就打出去。当所有的牌都打出去，手里剩余的牌还能在抽出一张

    // 法一 利用 set 数据结构
    // let set = new Set()
    // let m = 0
    // for (let i = 0; i < str.length; i++) {
    //   if (set.has(str[i])) {
    //     m += 2
    //     set.delete(str[i])
    //   } else {
    //     set.add(str[i])
    //   }
    // }

    // if (set.size > 1) {
    //   m += 1
    // }

    // return m

    // 法二 暴力破解
    let obj = {},
      m = 0;
    for (let i = 0; i < str.length; i++) {
      if (obj[str[i]]) {
        m += 2;
        delete obj[str[i]];
      } else {
        obj[str[i]] = str[i];
      }
    }

    if (JSON.stringify(obj) !== '{}') {
      m++;
    }

    return m;
  };
}

{
  // 1518. 换酒问题

  // 小区便利店正在促销，用 numExchange 个空酒瓶可以兑换一瓶新酒。你购入了 numBottles 瓶酒。
  // 如果喝掉了酒瓶中的酒，那么酒瓶就会变成空的。
  // 请你计算 最多 能喝到多少瓶酒。

  // 输入：numBottles = 9, numExchange = 3
  // 输出：13
  // 解释：你可以用 3 个空酒瓶兑换 1 瓶酒。
  // 所以最多能喝到 9 + 3 + 1 = 13 瓶酒。

  // 输入：numBottles = 15, numExchange = 4
  // 输出：19
  // 解释：你可以用 4 个空酒瓶兑换 1 瓶酒。
  // 所以最多能喝到 15 + 3 + 1 = 19 瓶酒。

  /* 
    @param {number} numBottles
    @param {number} numExchange
    @return {number}
  */
  let numWaterBottles = function (numBottles, numExchange) {
    if (numBottles < numExchange) return numBottles;
    if (numBottles === numExchange) return numBottles + 1;
    // 贪心算法
    let count = numBottles;
    while (numBottles >= numExchange) {
      let times = Math.floor(numBottles / numExchange); // 空瓶能兑换的酒
      let n = numBottles % numExchange; // 兑换完酒，余下的空瓶
      count += times;
      numBottles = times + n;
    }
    return count;

    // 可喝酒数count初始值为购买酒数量，即numBottles
    // 没喝掉n瓶，就把剩余的酒数减n，count+1
    // 循环条件为numBottles >= numExchange
    // 进入循环时，代表已经满足兑换酒的条件，所以剩余瓶数+1，直到剩余酒数不够兑换结束
    let count = numBottles;
    while (numBottles >= numExchange) {
      count++;
      numBottles++;
      numBottles -= numExchange;
    }
    return count;
  };
  console.log(numWaterBottles(9, 3));
  console.log(numWaterBottles(15, 4));
  console.log(numWaterBottles(5, 5));
  console.log(numWaterBottles(2, 3));
}

{
  // 39. 数组中出现次数超过一半的数字
  // 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
  // 你可以假设数组是非空的，并且给定的数组总是存在多数元素。

  // 示例 1:
  // 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
  // 输出: 2

  /**
   * @param {number[]} nums
   * @return {number}
   */
  let majorityElement = function (nums) {
    // 法一 利用对象属性
    // let o = {};
    // let res = 0
    // for (let i = 0; i < nums.length; i++) {
    //   const el = nums[i];
    //   if (o[el]) {
    //     o[el]++
    //   } else {
    //     o[el] = 1
    //   }

    //   if (o[el] > nums.length / 2) {
    //     res = el
    //   }
    // }
    // return res

    // 法二 利用sort排序
    nums.sort();
    return nums[Math.floor(nums.length / 2)];
  };
  console.log(majorityElement([1, 2, 3, 2, 2, 2, 5, 4, 2]));
}

{
  // 岛屿的周长
  // 给定一个包含 0 和 1 的二维网格地图，其中 1 表示陆地 0 表示水域。

  // 网格中的格子水平和垂直方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。

  // 岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

  // 示例:
  // 输入:
  // [[0, 1, 0, 0],
  // [1, 1, 1, 0],
  // [0, 1, 0, 0],
  // [1, 1, 0, 0]]
  // 输出: 16

  /**
   * @param {number[][]} grid
   * @return {number}
   */
  let islandPerimeter = function (grid) {
    // 法一 思路
    // 一块土地原则上周长是4，但是有接壤的土地，所以会剪掉2个边长
    // 所以总的周长 = 4 * 土地个数 - 2 * 接壤边的条数
    // 遍历矩阵，遍历到 land ++，如果它的右边或下边是土地，则 border ++
    // let land = 0;
    // let border = 0;
    // for (let i = 0; i < grid.length; i++) {
    //   for (let j = 0; j < grid[i].length; j++) {
    //     if (grid[i][j] === 1) {
    //       land++
    //       // 右边是土地
    //       if (j < grid[i].length - 1 && grid[i][j + 1] === 1) {
    //         border++
    //       }
    //       // 下边是土地
    //       if (i < grid.length - 1 && grid[i + 1][j] === 1) {
    //         border++
    //       }
    //     }
    //   }
    // }
    // return land * 4 - border * 2

    // 法二 上下左右
    // 一个小网格有四条边，求周长无非就是统计这四条边的数量，
    // 比如一个小网格的左边会不会被统计到周长里，要看这个小网格位于左边的什么位置，
    // 要么他的左侧没有别的小网格，这个时候把小网格的左侧边统计到周长里
    // j === 0 || grid[i][j-1] === 0

    let m = grid.length;
    if (m === 0) return 0;
    let n = grid[0].length;
    let res = 0;
    for (let i = 0; i < m; i++) {
      for (let j = 0; j < n; j++) {
        if (grid[i][j] === 1) {
          // 左边
          if (j === 0 || grid[i][j - 1] === 0) res++;
          // 上边
          if (i === 0 || grid[i - 1][j]) res++;
          // 右边
          if (j === m - 1 || grid[i][j + 1] === 0) res++;
          // 下边
          if (i === n - 1 || grid[i + 1][j] === 0) res++;
        }
      }
    }
    return res;
  };
  let grid = [
    [0, 1, 0, 0],
    [1, 1, 1, 0],
    [0, 1, 0, 0],
    [1, 1, 0, 0],
  ];
  console.log(islandPerimeter(grid));
}

{
  // 1652. 拆炸弹
  // 你有一个炸弹需要拆除，时间紧迫！你的情报员会给你一个长度为 n 的 循环 数组 code 以及一个密钥 k 。
  // 为了获得正确的密码，你需要替换掉每一个数字。所有数字会 同时 被替换。

  // 如果 k > 0 ，将第 i 个数字用 接下来 k 个数字之和替换。
  // 如果 k < 0 ，将第 i 个数字用 之前 k 个数字之和替换。
  // 如果 k == 0 ，将第 i 个数字用 0 替换。
  // 由于 code 是循环的， code[n-1] 下一个元素是 code[0] ，且 code[0] 前一个元素是 code[n-1] 。

  // 给你 循环 数组 code 和整数密钥 k ，请你返回解密后的结果来拆除炸弹！

  // 示例 1：
  // 输入：code = [5,7,1,4], k = 3
  // 输出：[12,10,16,13]
  // 解释：每个数字都被接下来 3 个数字之和替换。解密后的密码为 [7+1+4, 1+4+5, 4+5+7, 5+7+1]。注意到数组是循环连接的。

  // 示例 2：
  // 输入：code = [1,2,3,4], k = 0
  // 输出：[0,0,0,0]
  // 解释：当 k 为 0 时，所有数字都被 0 替换。

  // 示例 3：
  // 输入：code = [2,4,9,3], k = -2
  // 输出：[12,5,6,13]
  // 解释：解密后的密码为 [3+9, 2+3, 4+2, 9+4] 。注意到数组是循环连接的。如果 k 是负数，那么和为 之前 的数字。

  /**
   * @param {number[]} code
   * @param {number} k
   * @returns {number[]}
   */
  let decrypt = function (code, k) {
    let result = new Array(code.length).fill(0);
    let len = code.length;
    if (k === 0) {
      return result;
    }

    for (let i = 0; i < len; i++) {
      let sum = 0;
      for (let j = 0; j < Math.abs(k); j++) {
        if (k > 0) {
          sum += code[(i + j + 1) % len];
        } else {
          sum += code[(i - j - 1 + len) % len];
        }
      }
      result[i] = sum;
    }

    return result;

    // if (k === 0) {
    //   return new Array(code.length).fill(0);
    // }

    // let result = []
    // if (k > 0) {
    //   for (let i = 0; i < code.length; i++) {
    //     result.push(code.reduce((prev, curr) => prev + curr, 0) - code[i])
    //   }
    // }

    // if (k < 0) {
    //   for (let i = 0; i < code.length; i++) {
    //     // 0 2 3 -2
    //     // 1 3 0 -2
    //     // 2 0 1 -2
    //     // 3 1 2 -2
    //     result.push(
    //       code.reduce((prev, curr, idx, arr) => {
    //         let n = (i + Math.abs(k)) % code.length;
    //         console.log(n, n + 1 === len ? 0 : n + 1);
    //         if ([n, n + 1 === len ? 0 : n + 1].includes(idx)) {
    //           return prev + curr
    //         }
    //         return prev
    //       }, 0)
    //     )
    //   }
    // }

    // return result
  };
  console.log(decrypt([5, 7, 1, 4], 3));
  console.log(decrypt([2, 4, 9, 3], -2));
  console.log(decrypt([1, 2, 3, 4], 0));
}

{
  // 1304. 和为零的N个唯一整数

  // 给你一个整数 n，请你返回 任意 一个由 n 个 各不相同 的整数组成的数组，并且这 n 个数相加和为 0 。

  // 示例 1：
  // 输入：n = 5
  // 输出：[-7,-1,1,3,4]
  // 解释：这些数组也是正确的 [-5,-1,1,2,3]，[-3,-1,2,-2,4]。

  // 示例 2：
  // 输入：n = 3
  // 输出：[-1,0,1]

  // 示例 3：
  // 输入：n = 1
  // 输出：[0]

  /**
   * @param {number} n
   * @return {number[]}
   */
  let sumZero = function (n) {
    // 法一 思路
    // 根据下标构建前 n-1个数
    // 然后最后一个数是前边数的和
    // if (n === 0) return [0]
    // let res = []
    // let sum = 0;
    // for (let i = 0; i < n - 1; i++) {
    //   res.push(i)
    //   sum += i
    // }
    // sum.push(-sum)
    // return res

    // 法二 思路
    // 每次向数组推入两个相反的数，若是奇数在推入一个0
    let res = n / 2 === 0 ? [] : [0];
    let len = Math.floor(n / 2);
    for (let i = 1; i <= len; i++) {
      res.push(i, -i);
    }
    return res;
  };
}

{
  // 989. 数组形式的整数加法
  // 对于非负整数 X 而言，X 的数组形式是每位数字按从左到右的顺序形成的数组。例如，如果 X = 1231，那么其数组形式为 [1,2,3,1]。
  // 给定非负整数 X 的数组形式 A，返回整数 X+K 的数组形式。

  // 示例 1：
  // 输入：A = [1,2,0,0], K = 34
  // 输出：[1,2,3,4]
  // 解释：1200 + 34 = 1234

  // 示例 2：
  // 输入：A = [2,7,4], K = 181
  // 输出：[4,5,5]
  // 解释：274 + 181 = 455

  // 示例 3：
  // 输入：A = [2,1,5], K = 806
  // 输出：[1,0,2,1]
  // 解释：215 + 806 = 1021

  // 示例 4：
  // 输入：A = [9,9,9,9,9,9,9,9,9,9], K = 1
  // 输出：[1,0,0,0,0,0,0,0,0,0,0]
  // 解释：9999999999 + 1 = 10000000000
  let addToArrayForm = function (A, K) {
    // 法一 用数组api实现
    // return (+A.join('') + K + '').split('').map((item) => +item);
    return (BigInt(A.join('')) + BigInt(K)).toString().split('');
  };
  console.log(addToArrayForm([1, 2, 0, 0], 34));
  console.log(addToArrayForm([2, 7, 4], 181));
  console.log(addToArrayForm([9, 9, 9, 9, 9, 9, 9, 9, 9, 9], 1));
}

{
  // 搜索插入位置
  // 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
  // 你可以假设数组中无重复元素
  // 示例 1:
  // 输入: [1,3,5,6], 5
  // 输出: 2
  //
  // 示例 2:
  // 输入: [1,3,5,6], 2
  // 输出: 1
  //
  // 示例 3:
  // 输入: [1,3,5,6], 7
  // 输出: 4
  //
  // 示例 4:
  // 输入: [1,3,5,6], 0
  // 输出: 0

  // 法一 简单查找
  var searchInsert = function (nums, target) {
    let i = 0;
    while (i < nums.length && nums[i] < target) {
      i++;
    }
    return i;
  };

  // 法二 双指针法 类似 二分查找
  var searchInsert = function (nums, target) {
    if (nums[0] > target) return 0;
    if (nums[nums.length - 1] < target) return nums.length;

    let start = 0;
    let end = nums.length - 1;

    while (start <= end) {
      const mid = Math.round((end + start) / 2);
      if (nums[mid] === target) {
        return mid;
      } else if (nums[mid] < target) {
        start = mid + 1;
      } else {
        end = mid - 1;
      }
    }

    return start;
  };

  // 法三 二分查找
  var searchInsert = function (nums, target) {
    let left = 0;
    let right = nums.length - 1;
    while (left <= right) {
      const mid = Math.round((left + right) / 2);
      if (nums[mid] === target) {
        return mid;
      } else if (nums[mid] < target) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    return left;
  };

  console.log(searchInsert([1, 3, 5, 6], 5));
  console.log(searchInsert([1, 3, 5, 6], 2));
  console.log(searchInsert([1, 3, 5, 6], 7));
}

{
  // 两个数组的交集 II
  // 给定两个数组，编写一个函数来计算它们的交集。
  // 示例 1：
  // 输入：nums1 = [1,2,2,1], nums2 = [2,2]
  // 输出：[2,2]
  // 示例 2:
  // 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]

  /**
   * @param {number[]} nums1
   * @param {number[]} nums2
   * @return {number[]}
   */

  // 法一 indexOf
  let intersect = function (nums1, nums2) {
    // 遍历长度小的数组
    let nums = nums1.length > nums2.length ? nums2 : nums1;
    // 用长度大的数组判断，是否存在元素
    let _nums = nums1.length < nums2.length ? nums2 : nums1;

    let res = [];
    for (var i = 0; i < nums.length; i++) {
      if (_nums.indexOf(nums[i]) > -1) {
        res.push(nums[i]);
      }
    }
    return res;
  };

  // 法二 双指针
  // 1 题目不要求交集的顺序 可以先对数组排序
  // 2 创建一个指针left指向nums1数组的首位，指针right指向nums2首位
  // 3 创建零时栈，用于存放交集
  // 4 开始比较left right指针的值大小，若不等，这数字小的指针前进（即向右意移动一位）
  // 5 若相等入栈
  // 若nums1和nums2有一方遍历完毕，代表另一方的剩余值是唯一的不会产生交集
  let intersect = function (nums1, nums2) {
    nums1.sort((a, b) => a - b);
    nums2.sort((a, b) => a - b);

    let left = 0;
    let right = 0;
    let res = [];
    while (left < nums1.length && right < nums2.length) {
      if (nums1[left] === nums2[right]) {
        res.push(nums1[left]);
        left++;
        right++;
      } else {
        nums1[left] > nums2[right] ? right++ : left++;
      }
    }
    return res;
  };

  // 法三 hash map
  // 为两个数组分别建立map，用来存储 num -> count 的健值对，统计每个数字出现的数量
  // 然后对其中一个map进行遍历，查看这个数字在两个数组中分别出现的数量，取出现在最最小的那个
  // 数量（比如数组1中出现了一次，数组2中出现了2次，那么交集应该 取一次），push到结果数组中即可
  let intersect = function (nums1, nums2) {
    let map1 = makeCountMap(nums1);
    let map2 = makeCountMap(nums2);
    let res = [];
    for (const [num, count] of map1) {
      let count1 = map1.get(num);
      let count2 = map2.get(num);
      if (count2) {
        const resCount = Math.min(count1, count2);
        for (let i = 0; i < resCount; i++) {
          res.push(num);
        }
      }
    }
    return res;
  };
  function makeCountMap(nums) {
    let map = new Map();
    for (let i = 0; i < nums.length; i++) {
      let num = nums[i];
      let count = map.get(num);
      if (count) {
        map.set(num, count + 1);
      } else {
        map.set(num, 1);
      }
    }
    return map;
  }

  console.log('intersect: ', intersect([1, 2, 2, 1], [2, 2]));
  console.log('intersect: ', intersect([4, 9, 5], [9, 4, 9, 8, 4]));
}

{
  // 用 JavaScript 写一个函数，输入 int 型，返回整数逆序后的字符串。如：输入
  // 整型 1234，返回字符串“4321”。要求必须使用递归函数调用，不能用全局变量,
  // 输入函数必须只有一个参数传入，必须返回字符串
  function fun(num) {
    let num1 = num / 10; // 整除
    let num2 = num % 10; // 余数
    if (num1 < 1) {
      return num;
    } else {
      num1 = Math.floor(num1);
      return `${num2}${fun(num1)}`;
    }
  }

  var a = fun(12345);
  console.log(a);
  console.log(typeof a);
}

{
  // 给你两个有序整数数组 num1 和 num2，请你将 num2 合并到 num1 中，使 num1 成为一个有序数组
  // 说明: 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
  // 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

  // 输入:
  var nums1 = [1, 2, 3],
    m = 3;
  var nums2 = [2, 5, 6],
    n = 3;
  // 输出: [1,2,2,3,5,6]

  // 法一 双指针
  // 定义两个指针，分别指向两个数组的尾部
  // 每次只对指针所指的元素比较，取其中较大的元素，把它从nums1的尾部往前面补
  // 注意nums1和nums2长度不一样的时候
  // 如果提前遍历完nums1，那么剩下nums2。这时nums1的头部就空出来了，直接把nums2补到nums1的前面即可
  // 如果提前遍历完nums2，那么剩下nums1。因为容器本身就是nums1，所以不用处理
  /**
   * @param {nums1[]} nums1
   * @param {number} m
   * @param {nums2[]} nums2
   * @param {number} n
   * @return {void}
   */
  const merge = (nums1, m, nums2, n) => {
    // 初始化两个指针i j和nums1尾部指针k
    var i = m - 1,
      j = n - 1,
      k = m + n - 1;

    // 两个数组没有遍历完，同步往前走
    while (i >= 0 && j >= 0) {
      // 比较 较大的元素 从nums1的尾部往前面补
      if (nums1[i] >= nums2[j]) {
        nums1[k] = nums1[i];
        i--;
        k--;
      } else {
        nums1[k] = nums2[j];
        j--;
        k--;
      }
    }
    // nums2 数组长的情况下，单独处理下
    while (j >= 0) {
      nums1[k] = nums2[j];
      j--;
      k--;
    }
  };
  merge(nums1, m, nums2, n);
  console.log('nums1: ', nums1);

  // 法二 利用 js 数组方法，巧妙的解法
  // nums1 = [...nums1.slice(0, m), ...nums2.slice(0, n)].sort((a, b) => a - b);
  // nums1 = nums1
  //   .slice(0, m)
  //   .concat(nums2.slice(0, n))
  //   .sort((a, b) => a - b);
}

{
  // 给定一个字符串 s，最多删除一个字符。判断是否能成为回文字符串
  // 输入: "aba"
  // 输出: True
  // 输入: "abca"
  // 输出: True
  // 注意: 字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。
  // 解析：
  // 初始化两个指针分别指向头部和尾部
  // 如果两个指针的字符相等，那么这两个字符符合回文串对称的特性，跳过往下走即可；
  // 如果两个字符不想等，可以删除一个试试，看是否相等，分别对左指针字符和右指针字符尝试跳过；
  // 如果是的是的话，那么意味着删除跳过的字符，整个字符串就是回文串
  const validPalindrome = (s) => {
    let i = 0;
    let j = s.length - 1;

    while (i < j && s[i] === s[j]) {
      i++;
      j--;
    }

    // 判断跳过左指针元素是否是回文
    if (isPalindrome(i + 1, j)) {
      return true;
    }

    // 判断跳过右指针元素是否是回文
    if (isPalindrome(i, j - 1)) {
      return true;
    }

    // 判断字符串是否是会文串
    function isPalindrome(start, end) {
      // 如果跳过还不是会文串，那就不符合
      while (start < end) {
        if (s[start] !== s[end]) {
          return false;
        }
        start++;
        end--;
      }
      return true;
    }

    return false;
  };
  console.log(validPalindrome('aba'));
  console.log(validPalindrome('abca'));
}

{
  // 给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
  // 示例
  // 输入:
  // nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3;
  // 输出:
  // [3, 3, 5, 5, 6, 7];
  // 首先解释下滑动窗口的位置，比如给出的这个示例,滑动窗口的位置分别有如下情况
  // [1 3 -1] -3 5 3 6 7   最大值3
  // 1 [3 -1 -3] 5 3 6 7   最大值3
  // 1 3 [-1 -3 5] 3 6 7   最大值5
  // 1 3 -1 [-3 5 3] 6 7   最大值5
  // 1 3 -1 -3 [5 3 6] 7   最大值6
  // 1 3 -1 -3 5 [3 6 7]   最大值7
  // 所以最终会输出 [3, 3, 5, 5, 6, 7]

  // 法一 js api
  function maxSlidingWindow(nums, k) {
    const result = [];
    const len = nums.length;
    for (let i = 0; i < len - 2; i++) {
      const max = Math.max(...nums.slice(i, i + k));
      result.push(max);
    }
    return result;
  }

  // 法二 双指针+遍历
  // 1在遍历数组的过程中，约束一个窗口--窗口的本质实质上就是一个范围，像这样 [1 3 -1] -3 5 3 6 7,范围被圈定在了前三个元素。
  // 2如果要约束范围，我们是不是可以想到可以利用双指针。所以这里我们可以定义一个左指针和一个右指针，分别指向窗口的两端即可.
  // 3这样处理之后，是不是我们直接把这个窗口里的数字取出来，遍历一遍，求出最大值，然后把最大值存进结果数组是不是就行了。这样第一个窗口的最大值就有了。
  // 4接着，求第二个窗口的最大值，是不是移动指针，重复上边的过程，第二个窗口的最大值也取到了.
  /**
   * @param {number[]} nums
   * @param {number} k
   * @return {number[]}
   */
  function maxSlidingWindow(nums, k) {
    const result = [];
    const len = nums.length;
    // 处理边界情况
    if (k === 0 || len === 0) return result;

    // 初始化双指针
    let left = 0;
    let right = k - 1;
    while (right < len) {
      // const max = Math.max(...nums.slice(left, left + k));
      const max = calMax(nums, left, right);
      result.push(max);
      left++;
      right++;
    }

    return result;
  }

  /**
   * 求数组中的最大值
   * @param {nums[]} arr
   * @param {number} left
   * @param {number} right
   * @return {number} maxNum
   */
  function calMax(arr, left, right) {
    let maxNum = arr[left];
    for (let i = left; i <= right; i++) {
      if (arr[i] > maxNum) {
        maxNum = arr[i];
      }
    }
    return maxNum;
  }

  console.log(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3));
}

{
  // 给定一个没有重复数字的序列，返回其所有可能的全排列。
  /**
    示例
    输入: [1,2,3]
    输出: [
    [1,2,3],
    [1,3,2],
    [2,1,3],
    [2,3,1],
    [3,1,2],
    [3,2,1]
    ]
  */
  // 深度优先遍历的方式处理
  /**
   * @param {number[]} nums
   * @return {number[]}
   */
  const permute = (nums) => {
    const len = nums.length;
    const cur = []; // 记录当前的排列内容
    const res = []; // 记录所有的排列顺序
    const visited = []; // 用来避免重复使用同一个数字
    // 定义dfs的函数，入参是坑位的索引，从0开始
    function dfs(nth) {
      // 如果遍历到不存在的坑位(第len+1个)，则说明到了递归的边界
      if (nth === len) {
        // 此时前len个坑位已经填满，将对应的排序记录下来
        res.push(cur.slice());
        // 结束当前递归分支
        return;
      }
      // 检查手里剩下的数字有哪些
      for (let i = 0; i < len; i++) {
        // 如果nums[i] 之前没有被其它坑位记录过，说明这个数字是剩下的数字
        if (!visited[nums[i]]) {
          // 给nums[i] 打个已经用过的标记
          visited[nums[i]] = 1;
          // 将nums[i] 推入当前排列
          cur.push(nums[i]);
          // 基于这一个排序继续往下一个坑
          dfs(nth + 1);
          // nums[i] 让出当前坑位
          cur.pop();
          // 下掉已经用过的标识
          visited[nums[i]] = 0;
        }
      }
    }
    dfs(0);
    return res;
  };
  console.log(permute([1, 2, 3]));
}

{
  // 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集
  // 输入： nums = [1,2,3]
  /* 
    输出
    [
    [3],
    [1],
    [2],
    [1,2,3],
    [1,3],
    [2,3],
    [1,2],
    []
    ]
  */
  const subsets = function (nums) {
    // 存放结果
    const res = [];
    const len = nums.length;
    // 存放组合的数组
    const subset = [];
    // 进入dfs
    dfs(0);
    // 定义def,入参是nums中的数字索引
    function dfs(index) {
      // 每次进入意味着组合内容更新了一次，所以直接推入结果数组
      res.push(subset.slice());
      // 从当前数字索引开始，遍历数组
      for (let i = index; i < len; i++) {
        // 这里是当前数字存在于组合中的情况
        subset.push(nums[i]);
        // 基于当前数字存在于组合中的情况，进一步dfs
        dfs(i + 1);
        // 当前数字不存在数字组合的情况
        subset.pop();
      }
    }
    return res;
  };
  console.log(subsets([1, 2, 3]));
}

{
  // 实现 10 进制转换为 36 进制
  function baseConverter(decNumber, base) {
    return decNumber.toString(base);
  }
  // number 为传入的要转换的十进制数字
  // base: 要转成的进制类型
  function baseConverter(number, base) {
    if (!(base >= 2 && base <= 36)) {
      throw new Error('base argument must be between 2 and 36');
    }
    if (!Number.isInteger(number)) {
      throw new Error('目前不支持小数转换');
    }
    if (number === 0) {
      return 0;
    }
    const arr = [];
    // 定义一个进制位数，这里设置了 36 位进制，可自定义位数
    const digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
    // 存储符号
    let neg = '';
    if (number < 0) {
      neg = '-';
      number = Math.abs(number);
    }
    while (number) {
      // 获得10进制转换为36进制的最低位的值
      const res = Math.floor(number % base);
      // 存入首位
      arr.unshift(digits[res]);
      // number 进位，处理更高位的值
      number = Math.floor(number / base);
    }

    arr.unshift(neg);
    return arr.join('');
  }
  console.log(baseConverter(1314, 2)); // 10100100010
  console.log(baseConverter(1314, 8)); // 2442
  console.log(baseConverter(1314, 16)); // 522
  console.log(baseConverter(1314, 20)); // 35E
  console.log(baseConverter(1314, 30)); // 1DO
  console.log(baseConverter(1314, 36)); // 10i
}

{
  // 给定一个数组，按找到每个元素右侧第一个比它大的数字，没有的话返回-1 规则返回一个数组

  // 法一 暴力双循环
  function findMaxRight(nums) {
    const res = [];
    for (let i = 0; i < nums.length; i++) {
      for (let j = i + 1; j < nums.length; j++) {
        if (nums[j] > nums[i]) {
          res[i] = nums[j];
          break;
        } else {
          res[i] = -1;
        }
      }
    }
    res[nums.length - 1] = -1; // 最后一位处理
    return res;
  }
  var T = [2, 6, 3, 8, 10, 9];
  console.log(findMaxRight(T)); // [6, 8, 8, 10, -1, -1]

  // 法二 利用栈的特性
  function findMaxRight(array) {
    let result = [];
    for (let i = 0; i < array.length - 1; i++) {
      for (let j = i + 1; j < array.length; j++) {
        if (array[j] > array[i]) {
          result[i] = array[j];
          break;
        } else {
          result[i] = -1;
        }
      }
    }
    result[result.length] = -1;
    return result;
  }

  // 法三 单调递减栈, 反向遍历
  const firstBiggerItem = (T) => {
    const res = new Array(T.length).fill(-1);
    const stack = [];
    for (let i = T.length - 1; i >= 0; i--) {
      while (stack.length && T[i] >= T[stack[stack.length - 1]]) {
        stack.pop();
      }
      if (stack.length && T[i] < T[stack[stack.length - 1]]) {
        res[i] = T[stack[stack.length - 1]];
      }
      stack.push(i);
    }
    return res;
  };
}

{
  // 给定一个非法负整数nums，重新排列他们数字的每个顺序（每个数字不可拆分），使之组成一个最大的数字

  // 思路
  // 拆分数组 以10为界限
  // 然后定义双指针，分别冲两个数组左边开始比较
  function sort(arr) {
    let arr1 = arr.filter((o) => o < 10).sort((a, b) => b - a);
    let arr2 = arr.filter((o) => o >= 10).sort((a, b) => b - a);

    let len1 = arr1.length;
    let len2 = arr2.length;
    let i = 0;
    let j = 0;

    let str = '';

    while (len1 > i && len2 > j) {
      let s = ('' + arr1[i]).padEnd(('' + arr2[j]).length, '0');
      if (s >= arr2[j]) {
        str += arr1[i];
        i++;
      } else {
        str += arr2[j];
        j++;
      }
    }

    if (i < len1) {
      str += arr1.slice(i);
    }
    if (j < len2) {
      str += arr2.slice(j);
    }

    return +str;
  }
  console.log(sort([3, 5, 30, 34, 9]));
  console.log(sort([10, 2]));
}

{
  // 实现一个函数findLastIndex(), 返回指定数在“有序”数组中最后一次出现位置的索引。
  // 如 findLastIndex([1,2,3,3,3,4,5], 3), 返回 4。时间复杂度是多少？什么情况下时间复杂度最高？
  // 法一 二分查找法，对于重复数字的处理再用逼近方法，基本就可以得出答案了。时间复杂度时 o(logn)。
  function findLastIndex(nums, target) {
    let len = nums.length;
    let left = 0;
    let right = len - 1;

    while (true) {
      if (target < nums[left] || target > nums[right]) {
        return -1;
      }

      let midd = Math.floor((left + right) / 2);

      if (target === nums[midd]) {
        left = midd;
      } else if (target > nums[midd]) {
        right = midd;
      } else {
        right = midd;
      }

      if (left + 1 === right && nums[left] === target) {
        return left;
      }

      if (left + 1 === right && nums[right] === target) {
        return right;
      }
    }
  }
  function findLastIndex(nums, target) {
    let len = nums.length;
    if (len.length < 1) {
      return -1;
    }

    let l = 0;
    let r = len;

    while (l < r) {
      let mid = (l + r) >> 1; // let mid = Math.floor((l + r) / 2);
      target < nums[mid] ? (r = mid) : (l = mid + 1);
    }

    return l - 1;
  }
  // 法二 暴力法破解，时间复杂度将是 o(n)。最复杂的情况是数组全部遍历之后才能得出最终结果.
  function findLastIndex(nums, target) {
    let len = nums.length;
    if (len.length < 1) {
      return -1;
    }

    let k = 0;
    for (let i = 0; i < len; i++) {
      if (nums[i] === target) {
        k = i;
      }
    }

    return k;
  }
  console.log(findLastIndex([1, 2, 3, 3, 3, 4, 5], 3));
}

{
  // 求平方根
  // 给定一个非负整数 x ，计算并返回 x 的平方根，即实现 int sqrt(int x) 函数。
  // 正数的平方根有两个，只输出其中的正数平方根。
  // 如果平方根不是整数，输出只保留整数的部分，小数部分将被舍去。
  //
  // 示例 1:
  // 输入: x = 4
  // 输出: 2
  //
  // 示例 2:
  // 输入: x = 8
  // 输出: 2
  // 解释: 8 的平方根是 2.82842...，由于小数部分将被舍去，所以返回 2

  // 法一 二分查找
  function mySqrt(x) {
    if (x === 0 || x === 1) {
      return x;
    }

    let left = 0;
    let right = x;

    while (left <= right) {
      let mid = Math.floor((left + right) / 2);
      if (mid * mid === x) {
        return mid;
      } else if (mid * mid < x) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }

    return right;
  }

  // 法二 双指针
  function mySqrt(x) {
    if (x === 0 || x === 1) {
      return x;
    }

    let left = 0;
    let right = x;
    let res = -1;

    while (left <= right) {
      let mid = Math.floor((left + right) / 2);
      if (mid * mid <= x) {
        res = mid;
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }

    return res;
  }

  // 法三 js api
  function mySqrt(x) {
    return Math.floor(Math.sqrt(x));
  }
}

{
  // 输入50a6we8y20x
  // 输出50个a，6个we，8个y，20个x
  function print(str) {
    return String(str).replace(
      /(\d+)([a-zA-Z]+)/g,
      function (_, number, string) {
        return string.repeat(number);
      }
    );
  }
  console.log(print('50a6we8y20x'));
}

{
  // 实现es6字符串模板方法sprintf
  const template = "My name is ${name},I'm from ${city}";
  const result = sprintf(template, { name: 'Yiming Zhang', city: 'FuJian' });
  console.log(result); // My name is Yiming Zhang,I'm from FuJian

  function sprintf(str, data) {
    let newStr = str;
    Object.entries(data).forEach(([key, value]) => {
      newStr = newStr.replace(new RegExp('\\${' + key + '}'), value);
    });
    return newStr;
  }
}
